【题解】 [NOI2014]魔法森林 动态加边Spfa bzoj3669/luogu2387 | Qiuly's blog!

【题解】 [NOI2014]魔法森林 动态加边Spfa bzoj3669/luogu2387

Posted on | Edited on | In | Comments:

膜法森林2333……

显然是一道 $LCT$ 动态加边的题目。

然而并不需要这么高深的数据结构来动态加边(实际上是不会)，我们只需要 $Spfa$ 动态加边即可切掉此题。

怎么 $Spfa$?又是个怎么的动态加边法呢？

在下面我先给出代码，然后再来一步一步剖析(跟 $Spfa$ 板子差不多)。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#define ll long long
#define RI register int

const int N=5e4+2,M=1e5+2;
const int inf=1e9+9;

template <typename _Tp> inline void IN(_Tp&x){
    bool flag=0;char ch;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
}

bool vis[N];
std::queue<int> q;
int head[N],dis[N],tot,cnt,ans,n,m;
struct Edge_Spfa{int nxt,to,v1,v2;}G[M];
struct Edge_Main{
	int x,y,v1,v2;
	bool operator < (Edge_Main a)const{
	    return v1<a.v1;
	}
}L[M];

inline void make_line(int x,int y,int v1,int v2){
    G[++tot].nxt=head[x],head[x]=tot,G[tot].to=y,G[tot].v1=v1,G[tot].v2=v2;
    G[++tot].nxt=head[y],head[y]=tot,G[tot].to=x,G[tot].v1=v1,G[tot].v2=v2;
} 

#define A printf("A")
#define C printf("\n")
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
 
inline void spfa(int star_1,int star_2){
    vis[star_1]=true,vis[star_2]=true;
    q.push(star_1),q.push(star_2);
    while(!q.empty()){
        int u=q.front();q.pop();
		for(int i=head[u];i;i=G[i].nxt){
		    int to=G[i].to;
		    if(max(dis[u],G[i].v2)<dis[to]){
		        dis[to]=max(dis[u],G[i].v2);
				if(!vis[to])q.push(to),vis[to]=true; 
		    }
		}vis[u]=false;
    }return;
}

int main(){
    IN(n),IN(m);
    memset(dis,127,sizeof(dis));
    dis[1]=0,q.push(1),ans=inf; 
    for(int i=1;i<=m;++i)
	   IN(L[i].x),IN(L[i].y),IN(L[i].v1),IN(L[i].v2);
    std::sort(L+1,L+1+m);
	for(int i=1;i<=m;++i){
	    make_line(L[i].x,L[i].y,L[i].v1,L[i].v2);
		spfa(L[i].x,L[i].y);
		ans=min(ans,dis[n]+L[i].v1); 
	}printf("%d\n",ans==inf?-1:ans);
    return 0;
}

动态加边，顾名思义，就是按最优顺序依次将边插入，对于每次插完边的图做一次答案统计($Spfa$)，然后每次在 $main$ 函数里统计答案，最后输出即可。

我们固定 $v1$ ，用 $v2$ 跑 $Spfa$，边的插入顺序是按照 $v1$ 的大小来的，小的先插。

之所以上面要用到 $sort$，是因为我们要达到”按最优顺序依次将边插入”。

$Spfa$ 的板子就不解释了，不懂的同学左转搜素 $Spfa$ ，先刷几道黄牌去吧……

我们来看看动态加边的过程:

1
2
3
4
5
for(int i=1;i<=m;++i){
    make_line(L[i].x,L[i].y,L[i].v1,L[i].v2);
	spfa(L[i].x,L[i].y);
	ans=min(ans,dis[n]+L[i].v1); 
}

make_line(L[i].x,L[i].y,L[i].v1,L[i].v2); :

  • 加边，不解释

spfa(L[i].x,L[i].y); :

  • $Spfa$ 过程。

    • $Q$ :为什么要定义两个起点 $L[i].x$ 和 $L[i].y$ 呢？

    • $A$ :显然加进来了这条边后，对当前图中一些点的 $dis$ 值可能会有影响，所以以这个边的两端的点为起点，依次更新旁边的点，直到不能再更新。

ans=min(ans,dis[n]+L[i].v1); :

  • 更新 $ans$ 值

    • $Q$ :为什么使用 $dis[n]+L[i].v1$ 对 $ans$ 进行更新，有可能这条最短路上并不包含这个边啊，为什么要将 $L[i].v1$ 算进去呢？可能会更新错答案啊。

    • $A$ :对于当前图的最短路，我们分两种情况来讨论：

      • $1.$ 这条最短路上没包含这条新加上的边
      • $2.$ 这条最短路上包含了这条新加上的边

    • 对于第一种情况，显然这条最短路在加上这条边之前就已经有了，因为这条边的存在跟这条最短路没任何关系，既然之前有了，那么就肯定已经更新过 $ans$ 了。而那个时候的 $v1$ 是肯定比这个时候的 $v1$ 小的，也就是说 $ans$ 在之前已经被比现在的答案更小的答案更新过了，所以 $ans$ 也不会被当前答案更新。

    • 对于第二种情况，因为这条最短路上包含了这条边，而这条边肯定是这条最短路上 $v1$ 最大的边(当然也是当前图上 $v1$ 最大的边)，所以直接更新没错。

  • 每一次循环后数组不要重置吗？

    • 显然队列是不要的，因为 $Spfa$ 的退出条件是是队列为空，所以每次做完 $Spfa$ 时队列也就空了。

    • $vis$ 数组也不需要，跟队列是一个道理，只有 $vis$ 数组里面还有 $true$ 的元素，说明还有元素在队列里，队列空了，$vis$ 数组也自然空了。

    • $dis$ 数组不需要，因为循环中每次跑 $Spfa$ 是为了更新 $dis$ 数组而非做最短路。

然后……然后就没有然后了……

本文标题:【题解】 [NOI2014]魔法森林 动态加边Spfa bzoj3669/luogu2387

文章作者:Qiuly

发布时间:2019年02月13日 - 00:00

最后更新:2019年03月29日 - 13:53

原始链接:http://qiulyblog.github.io/2019/02/13/[题解]luoguP2387/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。